package svc.elib.socnet;

import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;

import edu.uci.ics.jung.graph.UndirectedSparseGraph;

import svc.elib.db.Author;
import svc.elib.util.Distribution;

/**
 * Resolves connected components
 * 
 * @author svc
 * @date 7.6.2013
 */
public class ConnectedComponents {
	
	private UndirectedSparseGraph<Author, Link> g;
	
	/**
	 * List of connected components
	 */
	private LinkedList<Net> components = new LinkedList<Net>();
	
	private HashSet<Author> visited = new HashSet<Author>();
	
	private int numComponents = 0;
	
	
	public ConnectedComponents(Net net) {
		g = net.getGraph();
	}
	
	public void resolveComponents() {
		Collection<Author> authors = g.getVertices();
		Iterator<Author> it = authors.iterator();
		while (it.hasNext()) {
			Author a = it.next();
			if (!visited.contains(a)) {
				int aDeg = g.degree(a);
				if (aDeg > 0) {
					++numComponents;
					Net comp = resolveComponent(a, numComponents);
					components.addLast(comp);
				}
			}
		}
		
		checkComponents();
		Collections.sort(components);
	}
	
	public Net resolveComponent(Author start, int componentId) {
		LinkedList<Author> q = new LinkedList<Author>();
		q.add(start);
		visited.add(start);
		
		Net comp = new Net("Comp_" + numComponents);
		comp.createNode(start);
		
		while (!q.isEmpty()) {
			Author a = q.removeFirst();
			
			Collection<Author> neic = g.getNeighbors(a);
			Iterator<Author> it = neic.iterator();
			while (it.hasNext()) {
				Author n = it.next();
				boolean nVisited = visited.contains(n);
				if (!nVisited) {
					q.addLast(n);
					comp.createNode(n);
					comp.createLink(a, n);
					visited.add(n);
				} else {
					comp.createLink(a, n);
				}
			}
		}
		
		return comp;
	}
	
	/**
	 * after connected components are determined the sum of links in components
	 * must be equal to the number of links in the network
	 */
	private void checkComponents() {
		int totalLinks = 0;
		for (int i = 0; i < components.size(); i++) {
			Net comp = components.get(i);
			totalLinks += comp.getGraph().getEdgeCount();
		}
		
		if (totalLinks != g.getEdgeCount()) {
			System.out.println("Error in connected component resolution");
			System.out.println("# links in original graphs : " + g.getEdgeCount());
			System.out.println("# total links in components: " + totalLinks);
		}
	}

	public void componentsInfo() {
		System.out.println("\nComponent info: ");
		System.out.println("# components = " + numComponents);
		System.out.println("Component size distribution -- ");
		
		LinkedList<Integer> cSize = new LinkedList<Integer>();
		for (int i = 0; i < components.size(); i++) {
			Net comp = components.get(i);
			int compSize = comp.getGraph().getVertexCount();
			cSize.add(compSize);
		}
		
		Distribution distr = new Distribution(cSize);
		distr.printDistr();
	}

	public LinkedList<Net> getComponents() {
		return components;
	}
	
	public int getNumComponents() {
		return components.size();
	}
	
	public double getLargestComponentSize() {
		//System.out.println("DEBUG: " + components.get(0).getNumAuthors() + ", " + g.getVertexCount());
		double f = (double) components.get(0).getNumAuthors() / (double) g.getVertexCount();
		int f100 = (int) (f * 100.0);
		return (double) f100 / 100.0;
	}
	
	public double avgComponentSize() {
		int sum = 0;
		for (int i = 0; i < components.size(); i++) {
			sum += components.get(i).getGraph().getVertexCount();
		}
		
		if (components.size() == 0)
			return 0.0;
		
		return (double) sum / (double) components.size();
	}
	
	public double avgComponentDensity() {
		double sumd = 0;
		for (int i = 0; i < components.size(); i++) {
			sumd += components.get(i).getDensity();
		}
		
		if (components.size() == 0)
			return 0.0;
		
		return sumd / (double) components.size();
	}
}
